package com.levi.sort;

/**
 * @author shentong
 * @date 2021/8/30 21:26
 * @Description 冒泡排序
 * 思路:
 * 1.一共有arr.length-1轮排序，
 * 2.每一轮又是一个循环，且每一轮的循环次数依次-1
 * 3.在每一轮的循环排序中，如果发现逆序的数字，则交换值
 * 注意:优化  如果有一次排序一次都没有交换，就说明已经排好序了，直接退出循环
 */
public class BubbleSort {

    public static void main(String[] args) {
//        int[] arr = {6, 4, 8, 2, 9, 1, 10, 3};
        int[] arr = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arr[i] = (int) (Math.random() * 80000);
        }
        long begin = System.currentTimeMillis();
        bubbleSort(arr);
        long end = System.currentTimeMillis();
//        long res = (end - begin) / 1000;

        System.out.printf("80000个数字用冒泡排序所消耗的时间是:%d毫秒\n",end-begin);//11100毫秒
//        print(arr);
    }

    /**
     * 冒泡排序
     */
    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length-1; i++) {
            int num = 0;//num用于计算交换的次数
            for (int j = 0; j < arr.length -i-1; j++) {
                //如果前面的比后面的大，就交换元素的值
                if (arr[j] > arr[j + 1]) {
                    num++;
                    var temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
            //如果这一次循环完了，交换的次数为0，说明已经排好序了，直接退出循环
            if (num == 0) {
                break;
            }
        }
    }

    /**
     * 打印数组
     */
    public static void print(int[] arr) {
        for (int i : arr) {
            System.out.print(i+" ");
        }
    }
}
